package com.fengkai.filepost.pdfoutstream.test.ODsolutions;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Fengkai
 * @creat 2023/4/20
 * 题目描述
 * 公园园区提供小火车单向通行，从园区站点编号最小到最大通行如1~2~3~4~1，然后供员工在各个办公园区穿梭，
 * 通过对公司N个员工调研统计到每个员工的坐车区间，包含前后站点，请设计一个程序计算出小火车在哪个园区站点时人数最多。
 * 输入描述：
 * 输入的第1个行，为调研员工人数第2行开始，
 * 为每个员工的开始上车站点和下车站点。
 * 使用数字代替每个园区用空格，分割如35表示从第3个园区上车，在第5个园区下车
 * 输出描述:
 * 人数最多时的园区站点编号，最多人数相同时返回编号最小的园区站点
 * 示例1：
 * 输入：
 * 3
 * 1 3
 * 2 4
 * 1 4
 * 输出：
 * 2
 * 说明：1号员工，在1站台上车，3站台下车。
 */
public class MostPeopleTrainStatus {
    public static void main (String[] args) {
        int n = 3;
        int[][] inputs = new int[][]{{1, 3}, {2, 4}, {1, 4},{4,5}};
        System.out.println(getMostPeopleStatus(n, inputs));

    }

    public static int getMostPeopleStatus (int n, int[][] inputs) {
        int result = 0;
        //先求出最大的站点
        int minStatus = 1;
        int maxStatus = 0;
        for (int[] input : inputs) {
            maxStatus = Math.max(maxStatus, input[0]);
            maxStatus = Math.max(maxStatus, input[1]);
        }
        //每个站点上的人数
        HashMap<Integer, Integer> statusPeoples = new HashMap<>();
        CyclicNode head = new CyclicNode(1);
        CyclicNode cache = head;
        for (int i = 1; i <= maxStatus; i++) {
            CyclicNode nextOne = new CyclicNode(i + 1);
            cache.setNext(i + 1 <= maxStatus ? nextOne : head);
            cache = nextOne;
            statusPeoples.put(i, 0);
        }

        for (int[] input : inputs) {
            CyclicNode cacheHead = head;

            int start = input[0];
            int end = input[1];
            boolean findHead = true;
            while (true) {
                if (findHead){
                    if (cacheHead.getValue() != start) {
                        cacheHead = cacheHead.getNext();
                        continue;
                    } else {
                        findHead = false;
                    }
                }
                statusPeoples.put(cacheHead.getValue(), statusPeoples.get(cacheHead.getValue()) + 1);
                if (cacheHead.getValue() == end) {
                    break;
                }
                cacheHead = cacheHead.getNext();
            }

        }
        int i = 1;
        for (Map.Entry<Integer, Integer> integerIntegerEntry : statusPeoples.entrySet()) {
            if (integerIntegerEntry.getValue() > statusPeoples.get(i)) {
                i = integerIntegerEntry.getKey();
            }
        }

        return i;
    }
}

class CyclicNode {
    private int value;
    private CyclicNode next;

    public CyclicNode (int value) {
        this.value = value;
    }

    public int getValue () {
        return value;
    }

    public void setValue (int value) {
        this.value = value;
    }

    public CyclicNode getNext () {
        return next;
    }

    public void setNext (CyclicNode next) {
        this.next = next;
    }
}
